// https://www.lintcode.com/problem/3sum-closest/description

class Solution {
public:
    /**
     * @param numbers: Give an array numbers of n integer
     * @param target: An integer
     * @return: return the sum of the three integers, the sum closest target.
     */
    int threeSumClosest(vector<int> &numbers, int target) {
        int closest = numbers[0] + numbers[1] + numbers[2];
        sort(numbers.begin(), numbers.end());
        for (int i = 0; i < numbers.size(); ++i)
        {
            int low = i + 1;
            int high = numbers.size() - 1;
            while (low < high)
            {
                int res = numbers[i] + numbers[low] + numbers[high];
                if (abs(res - target) < abs(closest - target)) closest = res;
                if (res > target) high--;
                else low++;
            }
        }
        return closest;
    }
};